package br.univap.aed.cenario1.sort;

import br.univap.aed.cenario1.utils.ListaEncadeada;
import br.univap.aed.cenario1.utils.Nodo;

public class QuickSortListaEncadeada {

	private int comparacoes = 0;
	private int copias = 0;

	public ListaEncadeada partition(ListaEncadeada lista, int pivo) {

		if (lista.tamanho() <= 1) {
			return lista;
		}

		ListaEncadeada L = new ListaEncadeada();
		ListaEncadeada E = new ListaEncadeada();
		ListaEncadeada G = new ListaEncadeada();

		Nodo x, y;

		x = lista.pega(pivo);
		lista.remove(pivo);

		E.adiciona(x);

		while (!lista.isEmpty()) {
			y = lista.pega(0);
			lista.remove(0);

			if (y.getKey() < x.getKey()) {
				L.adiciona(y);
				comparacoes++;
			} else if (y.getKey() == x.getKey()) {
				E.adiciona(y);
				comparacoes += 2;
			} else if (y.getKey() > x.getKey()) {
				G.adiciona(y);
				comparacoes += 3;
			}
		}

		lista = merge(partition(L, L.tamanho() - 1), E,
				partition(G, G.tamanho() - 1));
		return lista;
	}

	private ListaEncadeada merge(ListaEncadeada L, ListaEncadeada E,
			ListaEncadeada G) {

		ListaEncadeada lista = new ListaEncadeada();

		while (!L.isEmpty()) {
			lista.adiciona(L.removeNoComeco());
		}

		while (!E.isEmpty()) {
			lista.adiciona(E.removeNoComeco());
		}

		while (!G.isEmpty()) {
			lista.adiciona(G.removeNoComeco());
		}
		
		copias++;
		return lista;
	}

	public int getComparacoes() {
		return this.comparacoes;
	}

	public int getCopias() {
		return this.copias;
	}

}
